namespace System.Algorithm;

/// <summary>
/// Encapsulates a list of methods to handle with bits, using SIMD.
/// </summary>
/// <seealso href="https://learn.microsoft.com/en-us/dotnet/standard/simd">Microsoft Learn - SIMD</seealso>
/// <seealso href="https://en.wikipedia.org/wiki/Single_instruction,_multiple_data">Wikipedia - SIMD</seealso>
public static unsafe class SimdOperations
{
	/// <summary>
	/// Iterates all possible set bits in the target array.
	/// </summary>
	/// <param name="array">The array specified as a pointer that points to an array or other collection, of <see cref="long"/> integers.</param>
	/// <param name="length">The length of the argument <paramref name="array"/>.</param>
	/// <param name="outBuffer">The set bit indices specified as a buffer.</param>
	/// <returns>Returns the number of set bit indices. This return value is used with argument <paramref name="outBuffer"/>.</returns>
	/// <seealso href="https://lemire.me/blog/2018/03/08/iterating-over-set-bits-quickly-simd-edition/">
	/// Iterating over set bits quickly (SIMD edition)
	/// </seealso>
	public static int IterateBits(long* array, int length, int* outBuffer)
	{
		var baseVector = Vector256.Create(-1); // _mm256_set1_epi32
		var steppingVector = Vector256.Create(64); // _mm256_set1_epi32
		var add8 = Vector256.Create(8); // _mm256_set1_epi32
		var initOut = outBuffer;

		for (var i = 0; i < length; i++)
		{
			var w = array[i];
			if (w == 0)
			{
				baseVector += steppingVector; // _mm256_add_epi32
			}
			else
			{
				for (var k = 0; k < 4; k++)
				{
					var byteA = (byte)w;
					var byteB = (byte)(w >> 8);
					w >>= 16;

					if (byteA == 0 && byteB == 0)
					{
						continue;
					}

					fixed (int* pByteA = Constants.BitPosTable[byteA], pByteB = Constants.BitPosTable[byteB])
					{
						var vectorA = Vector256.Load(pByteA); // _mm256_load_si256
						var vectorB = Vector256.Load(pByteB); // _mm256_load_si256
						vectorA = baseVector + vectorA; // _mm256_add_epi32
						baseVector += add8; // _mm256_add_epi32
						vectorB = baseVector + vectorB; // _mm256_add_epi32
						baseVector += add8; // _mm256_add_epi32

						var advanceA = Constants.LengthTable[byteA];
						var advanceB = Constants.LengthTable[byteB];
						vectorA.Store(outBuffer); // _mm256_storeu_si256
						outBuffer += advanceA; // _mm256_add_epi32

						if (byteB == 0)
						{
							continue;
						}

						vectorB.Store(outBuffer); // _mm256_storeu_si256
						outBuffer += advanceB; // _mm256_add_epi32
					}
				}
			}
		}

		return (int)(outBuffer - initOut);
	}
}

/// <include file='../../global-doc-comments.xml' path='g/csharp11/feature[@name="file-local"]/target[@name="class" and @when="constant"]'/>
file static class Constants
{
#pragma warning disable format
	/// <summary>
	/// The length table. Indicates how many bits are set in the specified integer.
	/// </summary>
	public static readonly int[] LengthTable = [
		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
	];
#pragma warning restore format

	/// <summary>
	/// The bit position table. In other words, <c>BitPosTable[n]</c> means the n-th integer's (i.e. <c>n</c>'s) set bit positions
	/// represented as indices.
	/// </summary>
	public static readonly int[][] BitPosTable = [
		[0, 0, 0, 0, 0, 0, 0, 0],
		[1, 0, 0, 0, 0, 0, 0, 0],
		[2, 0, 0, 0, 0, 0, 0, 0],
		[1, 2, 0, 0, 0, 0, 0, 0],
		[3, 0, 0, 0, 0, 0, 0, 0],
		[1, 3, 0, 0, 0, 0, 0, 0],
		[2, 3, 0, 0, 0, 0, 0, 0],
		[1, 2, 3, 0, 0, 0, 0, 0],
		[4, 0, 0, 0, 0, 0, 0, 0],
		[1, 4, 0, 0, 0, 0, 0, 0],
		[2, 4, 0, 0, 0, 0, 0, 0],
		[1, 2, 4, 0, 0, 0, 0, 0],
		[3, 4, 0, 0, 0, 0, 0, 0],
		[1, 3, 4, 0, 0, 0, 0, 0],
		[2, 3, 4, 0, 0, 0, 0, 0],
		[1, 2, 3, 4, 0, 0, 0, 0],
		[5, 0, 0, 0, 0, 0, 0, 0],
		[1, 5, 0, 0, 0, 0, 0, 0],
		[2, 5, 0, 0, 0, 0, 0, 0],
		[1, 2, 5, 0, 0, 0, 0, 0],
		[3, 5, 0, 0, 0, 0, 0, 0],
		[1, 3, 5, 0, 0, 0, 0, 0],
		[2, 3, 5, 0, 0, 0, 0, 0],
		[1, 2, 3, 5, 0, 0, 0, 0],
		[4, 5, 0, 0, 0, 0, 0, 0],
		[1, 4, 5, 0, 0, 0, 0, 0],
		[2, 4, 5, 0, 0, 0, 0, 0],
		[1, 2, 4, 5, 0, 0, 0, 0],
		[3, 4, 5, 0, 0, 0, 0, 0],
		[1, 3, 4, 5, 0, 0, 0, 0],
		[2, 3, 4, 5, 0, 0, 0, 0],
		[1, 2, 3, 4, 5, 0, 0, 0],
		[6, 0, 0, 0, 0, 0, 0, 0],
		[1, 6, 0, 0, 0, 0, 0, 0],
		[2, 6, 0, 0, 0, 0, 0, 0],
		[1, 2, 6, 0, 0, 0, 0, 0],
		[3, 6, 0, 0, 0, 0, 0, 0],
		[1, 3, 6, 0, 0, 0, 0, 0],
		[2, 3, 6, 0, 0, 0, 0, 0],
		[1, 2, 3, 6, 0, 0, 0, 0],
		[4, 6, 0, 0, 0, 0, 0, 0],
		[1, 4, 6, 0, 0, 0, 0, 0],
		[2, 4, 6, 0, 0, 0, 0, 0],
		[1, 2, 4, 6, 0, 0, 0, 0],
		[3, 4, 6, 0, 0, 0, 0, 0],
		[1, 3, 4, 6, 0, 0, 0, 0],
		[2, 3, 4, 6, 0, 0, 0, 0],
		[1, 2, 3, 4, 6, 0, 0, 0],
		[5, 6, 0, 0, 0, 0, 0, 0],
		[1, 5, 6, 0, 0, 0, 0, 0],
		[2, 5, 6, 0, 0, 0, 0, 0],
		[1, 2, 5, 6, 0, 0, 0, 0],
		[3, 5, 6, 0, 0, 0, 0, 0],
		[1, 3, 5, 6, 0, 0, 0, 0],
		[2, 3, 5, 6, 0, 0, 0, 0],
		[1, 2, 3, 5, 6, 0, 0, 0],
		[4, 5, 6, 0, 0, 0, 0, 0],
		[1, 4, 5, 6, 0, 0, 0, 0],
		[2, 4, 5, 6, 0, 0, 0, 0],
		[1, 2, 4, 5, 6, 0, 0, 0],
		[3, 4, 5, 6, 0, 0, 0, 0],
		[1, 3, 4, 5, 6, 0, 0, 0],
		[2, 3, 4, 5, 6, 0, 0, 0],
		[1, 2, 3, 4, 5, 6, 0, 0],
		[7, 0, 0, 0, 0, 0, 0, 0],
		[1, 7, 0, 0, 0, 0, 0, 0],
		[2, 7, 0, 0, 0, 0, 0, 0],
		[1, 2, 7, 0, 0, 0, 0, 0],
		[3, 7, 0, 0, 0, 0, 0, 0],
		[1, 3, 7, 0, 0, 0, 0, 0],
		[2, 3, 7, 0, 0, 0, 0, 0],
		[1, 2, 3, 7, 0, 0, 0, 0],
		[4, 7, 0, 0, 0, 0, 0, 0],
		[1, 4, 7, 0, 0, 0, 0, 0],
		[2, 4, 7, 0, 0, 0, 0, 0],
		[1, 2, 4, 7, 0, 0, 0, 0],
		[3, 4, 7, 0, 0, 0, 0, 0],
		[1, 3, 4, 7, 0, 0, 0, 0],
		[2, 3, 4, 7, 0, 0, 0, 0],
		[1, 2, 3, 4, 7, 0, 0, 0],
		[5, 7, 0, 0, 0, 0, 0, 0],
		[1, 5, 7, 0, 0, 0, 0, 0],
		[2, 5, 7, 0, 0, 0, 0, 0],
		[1, 2, 5, 7, 0, 0, 0, 0],
		[3, 5, 7, 0, 0, 0, 0, 0],
		[1, 3, 5, 7, 0, 0, 0, 0],
		[2, 3, 5, 7, 0, 0, 0, 0],
		[1, 2, 3, 5, 7, 0, 0, 0],
		[4, 5, 7, 0, 0, 0, 0, 0],
		[1, 4, 5, 7, 0, 0, 0, 0],
		[2, 4, 5, 7, 0, 0, 0, 0],
		[1, 2, 4, 5, 7, 0, 0, 0],
		[3, 4, 5, 7, 0, 0, 0, 0],
		[1, 3, 4, 5, 7, 0, 0, 0],
		[2, 3, 4, 5, 7, 0, 0, 0],
		[1, 2, 3, 4, 5, 7, 0, 0],
		[6, 7, 0, 0, 0, 0, 0, 0],
		[1, 6, 7, 0, 0, 0, 0, 0],
		[2, 6, 7, 0, 0, 0, 0, 0],
		[1, 2, 6, 7, 0, 0, 0, 0],
		[3, 6, 7, 0, 0, 0, 0, 0],
		[1, 3, 6, 7, 0, 0, 0, 0],
		[2, 3, 6, 7, 0, 0, 0, 0],
		[1, 2, 3, 6, 7, 0, 0, 0],
		[4, 6, 7, 0, 0, 0, 0, 0],
		[1, 4, 6, 7, 0, 0, 0, 0],
		[2, 4, 6, 7, 0, 0, 0, 0],
		[1, 2, 4, 6, 7, 0, 0, 0],
		[3, 4, 6, 7, 0, 0, 0, 0],
		[1, 3, 4, 6, 7, 0, 0, 0],
		[2, 3, 4, 6, 7, 0, 0, 0],
		[1, 2, 3, 4, 6, 7, 0, 0],
		[5, 6, 7, 0, 0, 0, 0, 0],
		[1, 5, 6, 7, 0, 0, 0, 0],
		[2, 5, 6, 7, 0, 0, 0, 0],
		[1, 2, 5, 6, 7, 0, 0, 0],
		[3, 5, 6, 7, 0, 0, 0, 0],
		[1, 3, 5, 6, 7, 0, 0, 0],
		[2, 3, 5, 6, 7, 0, 0, 0],
		[1, 2, 3, 5, 6, 7, 0, 0],
		[4, 5, 6, 7, 0, 0, 0, 0],
		[1, 4, 5, 6, 7, 0, 0, 0],
		[2, 4, 5, 6, 7, 0, 0, 0],
		[1, 2, 4, 5, 6, 7, 0, 0],
		[3, 4, 5, 6, 7, 0, 0, 0],
		[1, 3, 4, 5, 6, 7, 0, 0],
		[2, 3, 4, 5, 6, 7, 0, 0],
		[1, 2, 3, 4, 5, 6, 7, 0],
		[8, 0, 0, 0, 0, 0, 0, 0],
		[1, 8, 0, 0, 0, 0, 0, 0],
		[2, 8, 0, 0, 0, 0, 0, 0],
		[1, 2, 8, 0, 0, 0, 0, 0],
		[3, 8, 0, 0, 0, 0, 0, 0],
		[1, 3, 8, 0, 0, 0, 0, 0],
		[2, 3, 8, 0, 0, 0, 0, 0],
		[1, 2, 3, 8, 0, 0, 0, 0],
		[4, 8, 0, 0, 0, 0, 0, 0],
		[1, 4, 8, 0, 0, 0, 0, 0],
		[2, 4, 8, 0, 0, 0, 0, 0],
		[1, 2, 4, 8, 0, 0, 0, 0],
		[3, 4, 8, 0, 0, 0, 0, 0],
		[1, 3, 4, 8, 0, 0, 0, 0],
		[2, 3, 4, 8, 0, 0, 0, 0],
		[1, 2, 3, 4, 8, 0, 0, 0],
		[5, 8, 0, 0, 0, 0, 0, 0],
		[1, 5, 8, 0, 0, 0, 0, 0],
		[2, 5, 8, 0, 0, 0, 0, 0],
		[1, 2, 5, 8, 0, 0, 0, 0],
		[3, 5, 8, 0, 0, 0, 0, 0],
		[1, 3, 5, 8, 0, 0, 0, 0],
		[2, 3, 5, 8, 0, 0, 0, 0],
		[1, 2, 3, 5, 8, 0, 0, 0],
		[4, 5, 8, 0, 0, 0, 0, 0],
		[1, 4, 5, 8, 0, 0, 0, 0],
		[2, 4, 5, 8, 0, 0, 0, 0],
		[1, 2, 4, 5, 8, 0, 0, 0],
		[3, 4, 5, 8, 0, 0, 0, 0],
		[1, 3, 4, 5, 8, 0, 0, 0],
		[2, 3, 4, 5, 8, 0, 0, 0],
		[1, 2, 3, 4, 5, 8, 0, 0],
		[6, 8, 0, 0, 0, 0, 0, 0],
		[1, 6, 8, 0, 0, 0, 0, 0],
		[2, 6, 8, 0, 0, 0, 0, 0],
		[1, 2, 6, 8, 0, 0, 0, 0],
		[3, 6, 8, 0, 0, 0, 0, 0],
		[1, 3, 6, 8, 0, 0, 0, 0],
		[2, 3, 6, 8, 0, 0, 0, 0],
		[1, 2, 3, 6, 8, 0, 0, 0],
		[4, 6, 8, 0, 0, 0, 0, 0],
		[1, 4, 6, 8, 0, 0, 0, 0],
		[2, 4, 6, 8, 0, 0, 0, 0],
		[1, 2, 4, 6, 8, 0, 0, 0],
		[3, 4, 6, 8, 0, 0, 0, 0],
		[1, 3, 4, 6, 8, 0, 0, 0],
		[2, 3, 4, 6, 8, 0, 0, 0],
		[1, 2, 3, 4, 6, 8, 0, 0],
		[5, 6, 8, 0, 0, 0, 0, 0],
		[1, 5, 6, 8, 0, 0, 0, 0],
		[2, 5, 6, 8, 0, 0, 0, 0],
		[1, 2, 5, 6, 8, 0, 0, 0],
		[3, 5, 6, 8, 0, 0, 0, 0],
		[1, 3, 5, 6, 8, 0, 0, 0],
		[2, 3, 5, 6, 8, 0, 0, 0],
		[1, 2, 3, 5, 6, 8, 0, 0],
		[4, 5, 6, 8, 0, 0, 0, 0],
		[1, 4, 5, 6, 8, 0, 0, 0],
		[2, 4, 5, 6, 8, 0, 0, 0],
		[1, 2, 4, 5, 6, 8, 0, 0],
		[3, 4, 5, 6, 8, 0, 0, 0],
		[1, 3, 4, 5, 6, 8, 0, 0],
		[2, 3, 4, 5, 6, 8, 0, 0],
		[1, 2, 3, 4, 5, 6, 8, 0],
		[7, 8, 0, 0, 0, 0, 0, 0],
		[1, 7, 8, 0, 0, 0, 0, 0],
		[2, 7, 8, 0, 0, 0, 0, 0],
		[1, 2, 7, 8, 0, 0, 0, 0],
		[3, 7, 8, 0, 0, 0, 0, 0],
		[1, 3, 7, 8, 0, 0, 0, 0],
		[2, 3, 7, 8, 0, 0, 0, 0],
		[1, 2, 3, 7, 8, 0, 0, 0],
		[4, 7, 8, 0, 0, 0, 0, 0],
		[1, 4, 7, 8, 0, 0, 0, 0],
		[2, 4, 7, 8, 0, 0, 0, 0],
		[1, 2, 4, 7, 8, 0, 0, 0],
		[3, 4, 7, 8, 0, 0, 0, 0],
		[1, 3, 4, 7, 8, 0, 0, 0],
		[2, 3, 4, 7, 8, 0, 0, 0],
		[1, 2, 3, 4, 7, 8, 0, 0],
		[5, 7, 8, 0, 0, 0, 0, 0],
		[1, 5, 7, 8, 0, 0, 0, 0],
		[2, 5, 7, 8, 0, 0, 0, 0],
		[1, 2, 5, 7, 8, 0, 0, 0],
		[3, 5, 7, 8, 0, 0, 0, 0],
		[1, 3, 5, 7, 8, 0, 0, 0],
		[2, 3, 5, 7, 8, 0, 0, 0],
		[1, 2, 3, 5, 7, 8, 0, 0],
		[4, 5, 7, 8, 0, 0, 0, 0],
		[1, 4, 5, 7, 8, 0, 0, 0],
		[2, 4, 5, 7, 8, 0, 0, 0],
		[1, 2, 4, 5, 7, 8, 0, 0],
		[3, 4, 5, 7, 8, 0, 0, 0],
		[1, 3, 4, 5, 7, 8, 0, 0],
		[2, 3, 4, 5, 7, 8, 0, 0],
		[1, 2, 3, 4, 5, 7, 8, 0],
		[6, 7, 8, 0, 0, 0, 0, 0],
		[1, 6, 7, 8, 0, 0, 0, 0],
		[2, 6, 7, 8, 0, 0, 0, 0],
		[1, 2, 6, 7, 8, 0, 0, 0],
		[3, 6, 7, 8, 0, 0, 0, 0],
		[1, 3, 6, 7, 8, 0, 0, 0],
		[2, 3, 6, 7, 8, 0, 0, 0],
		[1, 2, 3, 6, 7, 8, 0, 0],
		[4, 6, 7, 8, 0, 0, 0, 0],
		[1, 4, 6, 7, 8, 0, 0, 0],
		[2, 4, 6, 7, 8, 0, 0, 0],
		[1, 2, 4, 6, 7, 8, 0, 0],
		[3, 4, 6, 7, 8, 0, 0, 0],
		[1, 3, 4, 6, 7, 8, 0, 0],
		[2, 3, 4, 6, 7, 8, 0, 0],
		[1, 2, 3, 4, 6, 7, 8, 0],
		[5, 6, 7, 8, 0, 0, 0, 0],
		[1, 5, 6, 7, 8, 0, 0, 0],
		[2, 5, 6, 7, 8, 0, 0, 0],
		[1, 2, 5, 6, 7, 8, 0, 0],
		[3, 5, 6, 7, 8, 0, 0, 0],
		[1, 3, 5, 6, 7, 8, 0, 0],
		[2, 3, 5, 6, 7, 8, 0, 0],
		[1, 2, 3, 5, 6, 7, 8, 0],
		[4, 5, 6, 7, 8, 0, 0, 0],
		[1, 4, 5, 6, 7, 8, 0, 0],
		[2, 4, 5, 6, 7, 8, 0, 0],
		[1, 2, 4, 5, 6, 7, 8, 0],
		[3, 4, 5, 6, 7, 8, 0, 0],
		[1, 3, 4, 5, 6, 7, 8, 0],
		[2, 3, 4, 5, 6, 7, 8, 0],
		[1, 2, 3, 4, 5, 6, 7, 8]
	];
}
